package pri.zjy.backTracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description 组合
 * <p>
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * @date 2025/6/12 17:16
 */
public class Combine_77 {

    public static void main(String[] args) {

    }

    /**
     * dmsxl-回溯
     * <p>
     * 思路：直接通过group.size()判断找到的目标元素个数
     * <p>
     * 分析：由题目可知，目标整数元素在[1, n]，是不重复的整数；
     * <p>
     * 1.为什么使用startIndex？<br/>
     * ——本题是在同一个集合中，找目标组合，那么对于{1,2}、{2,1}来说，这两个其实算同一个组合；所以，要通过startIndex知道已经收获过哪些元素，避免出现得到重复组合的情况。
     * <p>
     * 2.为什么for循环要从startIndex开始？<br/>
     * ——startIndex可以知道已经收获过哪些元素，但仍要结合，在for循环收集时要控制其跳过这些元素，才能真正避免得到重复组合的情况。所以实际上，通过1和2两点，一起才能实现得到不重复的组合。
     */
    List<List<Integer>> result = new ArrayList<>();

    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combine2(int n, int k) {
        backTracking2(n, k, 1);
        return result;
    }

    public void backTracking2(int n, int k, int startNum) {
        // 1.找齐k个数后，记录并返回
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }

        // 2.横向遍历，给每个元素找目标组合
        for (int i = startNum; i <= n; i++) {
            // 2.1.直接记录当前元素
            path.add(i);

            // 2.2.递归
            backTracking2(n, k, i + 1);

            // 2.3.已经找到并记录一个目标组合，把group最后一个元素移除，继续找目标组合
            path.remove(path.size() - 1);
        }
    }

    /**
     * 个解：回溯
     * <p>
     * 思路：可以画出该题的一个树结构，这样更加清晰
     * 1. k，表示本层递归还需要找多少个元素。
     * 2. startNum，就是防止出现重复的组合；因为组合，{1,2}和{2,1}是一样的，所以对于[1,2,3,4]，当1已经使用过，那么下一层递归就该从2开始，否则就会出现{2，1}
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        // 从1开始，因为1 <= n <= 20
        backTracking(n, k, ans, new ArrayList<>(), 1);

        return ans;
    }

    public void backTracking(int n, int k, List<List<Integer>> ans, List<Integer> group, int startNum) {
        // 1.找齐k个数后，记录并返回
        if (k == 0) {
            ans.add(new ArrayList<>(group));
            return;
        }

        // 2.横向遍历，给每个元素找目标组合
        for (int i = startNum; i <= n; i++) {
            // 2.1.直接记录当前元素
            group.add(i);

            // 2.2.递归
            // 已经记录一个元素，递归要找的元素个数为 k-1；每个元素不能重复使用，所以每层递归的循环开始数为 i+1。
            backTracking(n, k - 1, ans, group, i + 1);

            // 2.3.已经找到并记录一个目标组合，把group最后一个元素移除，继续找目标组合
            group.remove(group.size() - 1);
        }
    }

}
